package JZOffer;

import java.util.HashSet;
import java.util.PriorityQueue;

public class Jz49 {

    // Jz.49丑数
    public static int nthUglyNumber(int n) {

//        int num = 0, i = 0;
//        // 暴力遍历
//        for (i = 1; ; i++) {
//            if (i == 1) num++;
//            else {
//                if (i%2 == 0 || i%3 == 0 || i%5 == 0) {
//                    num++;
//                }
//            }
//            if(num == n) break;
//        }
//        return i;

        // 方法一：使用最小堆 +　集合去重
        int[] factors = new int[]{2,3,5};
        // 创建set集合用于去重
        HashSet<Long> set = new HashSet<>();
        PriorityQueue<Long> priorityQueue = new PriorityQueue<>();
        set.add(1l);
        priorityQueue.offer(1l);
        int ugly = 0;
        for (int i = 0; i < n; i++) {
            long cur = priorityQueue.poll();
            ugly = (int) cur;
            for (int factor : factors) {
                long next = cur * factor;
                if(set.add(next)) {
                    priorityQueue.offer(next);
                }
            }
        }
        return ugly;

        /**
         * LWZ TODO : 2021/9/26 方法二：动态规划
         *
         */

    }

    public static void main(String[] args) {
        int i = nthUglyNumber(11);
        System.out.println(i);
    }

}
